package com.LeeCode;

/**
 * 修剪二叉搜索树
 */

public class Code669 {
    public static void main(String[] args) {
        Integer[] arr = {3, 0, 4, null, 2, null, null, 1};
        TreeNode root = Utils.buildTree(arr);
        TreeNode node = new Code669().trimBST(root, 1, 3);
        System.out.println("done");
    }

    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;

        if (root.val < low) {
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        }

        if (root.left != null) {
            root.left = trimBST(root.left, low, high);
        }
        if (root.right != null) {
            root.right = trimBST(root.right, low, high);
        }

        return root;
    }
}
